package com.breeze.tree;

import java.util.LinkedList;
import java.util.Queue;

public class AVLTree {
    Node root;

    public void addData(int value) {
        root = addData(value, root);
    }
    private Node addData(int value, Node t) {
        if (t == null) {
            Node node = new Node(value);
            // 新增结点高度为0
            node.height = 0;
            return node;
        }
        if (value < t.value) {
            t.left = addData(value, t.left);
            if (height(t.left) - height(t.right) == 2) {
                // 左左型
                if (value < t.left.value) {
                    t = rRotate(t);
                } else {
                    // 左右型
                    t = lRRotate(t);
                }
            }
        } else {
            t.right = addData(value, t.right);
            if (height(t.right) - height(t.left) == 2) {
                // 右右型
                if (value > t.right.value) {
                    t = lRotate(t);
                } else {
                    // 右左型
                    t = rLRotate(t);
                }
            }
        }
        t.height = Math.max(height(t.left), height(t.right)) + 1;
        return t;
    }

    /**
     * 左旋
     *
     * @param t 需要调整的树
     * @return 调整后的树
     */
    public Node lRotate(Node t) {
        Node newTree = t.right;
        t.right = newTree.left;
        newTree.left = t;
        t.height = Math.max(height(t.left), height(t.right)) + 1;
        newTree.height = Math.max(height(newTree.left), height(newTree.right)) + 1;
        return newTree;
    }

    /**
     * 右旋
     *
     * @param t
     * @return
     */
    public Node rRotate(Node t) {
        Node newTree = t.left;
        t.left = newTree.right;
        newTree.right = t;
        t.height = Math.max(height(t.left), height(t.right)) + 1;
        newTree.height = Math.max(height(newTree.left), height(newTree.right)) + 1;
        return newTree;
    }

    /**
     * 先左旋再右旋
     *
     * @param t
     * @return
     */
    public Node lRRotate(Node t) {
        t.left = lRotate(t.left);
        return rRotate(t);
    }

    /**
     * 先右旋再左旋
     *
     * @param t
     * @return
     */
    public Node rLRotate(Node t) {
        t.right = rRotate(t.right);
        return lRotate(t);
    }

    /**
     * 获取当前树的高度
     *
     * @return
     */
    public int getHeight() {
        return height(root);
    }

    /**
     * 获取任意树的高度
     *
     * @param t
     * @return
     */
    private int height(Node t) {
        if (t == null) {
            return -1;
        } else {
            return t.height;
        }
    }

    /**
     * 层序遍历
     */
    public void showLevelOrder() {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.value + ",");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    class Node {
        int value;
        Node left, right;
        // 记录节点的高度
        int height;

        public Node(int value) {
            this.value = value;
        }
    }
}
